Exercise: Skiplists - Data Structures with Generic Types in Python

Task#

The find(x) method in a Skiplist sometimes performs redundant comparisons; these occur when x is compared to the same value more than once. They can occur when, for some node, u, u.next[r] = u.next[r − 1]. Modify the find(x) so that these redundant comparisons are avoided.

Sample input

The sample input will be as follows:

The first 25 values in a skiplist will be using this formula: i % 100 + 900
The next 50 values in a skiplist will be using this formula: i % 50
The next 25 values in a skiplist will be using this formula: i % 20

Expected output

The expected output will be as follows:

Adding 1000 elements
Searching
Found: 10 , 20 , None

main.py

base.py

utils.py

import random
from utils import new_array, numpy
from base import BaseSet
class SkiplistSSet(BaseSet):
    # Node class
    class Node(object):
        def __init__(self, x, h):
            self.x = x
            self.next = new_array(h+1)
        # Function to return height
        def height(self):
            return len(self.next) - 1
    # Function to create new node
    def _new_node(self, x, h):
        return SkiplistSSet.Node(x, h)
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
    # Initialize function    
    def _initialize(self):
        self.h = 0
        self.n = 0
        self.sentinel = self._new_node(None, 32)
        self.stack = new_array(self.sentinel.height()+1)
    # Function to reset the skiplist    
    def clear(self):
        self._initialize()
    # Function to find pred node
    def find_pred_node(self, x):

Enter to Rename, Shift+Enter to Preview

Solution to implement an efficient find() method